package leetcode.hash和set;

import java.util.*;

/**
 * 字母异位词分组
 * <p>
 * 使用 hash 表
 */
public class Test49字母异位词分组 {

    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }
        // 因为存在一致的字符，于是以字符为 key，字符组合为 value
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            // 先给每个字符串重新排序，得到相同顺序的字符串
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            // 然后得到 key
            String key = String.valueOf(c);
            // 如果 map 里面不存在此 key 就 put一个 key-value 进去
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            // 存在此 key 就为此 key 的 list 添加内容，内容为 String[] 里面的原始数据
            map.get(key).add(strs[i]);
        }
        // 最后只需要返回 map 里面的 value就可以了
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strings = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> ans = groupAnagrams(strings);
        ans.forEach((e) -> System.out.println(e));
    }
}
